package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

import static java.lang.Math.max;
import static java.lang.Math.min;

/**
 * @author tzp
 * @since 2020/9/17
 */
public class LC152_1 implements DynamicProblem {
    public int maxProduct(int[] nums) {
        int[] state = new int[nums.length];
        int[] state1 = new int[nums.length];
        state[0] = nums[0];
        state1[0] = nums[0];
        int max = state[0];
        for (int i = 1; i < nums.length; i++) {
            state[i] = max(max(nums[i], nums[i] * state[i - 1]), nums[i] * state1[i - 1]);
            state1[i] = min(min(nums[i], nums[i] * state[i - 1]), nums[i] * state1[i - 1]);
            max = max(max, state[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new LC152_1().maxProduct(new int[]{2, 3, -2, 4}));//6
        System.out.println(new LC152_1().maxProduct(new int[]{-2, 0, -1}));//0
        System.out.println(new LC152_1().maxProduct(new int[]{-2, 3, 4, -1}));//24
        System.out.println(new LC152_1().maxProduct(new int[]{-2}));//-2
        System.out.println(new LC152_1().maxProduct(new int[]{-1, -2, -9, -6}));//108
        //[-1,-2,-9,-6]
        //-1 2 18
        //-1 -2 -9
    }
}
